package me.renyaoxiang.algorithm.sort;


public class MergeSort {
    public static void sort(int[] data) {
        sortPart(data, 0, data.length);
    }

    public static void sortPart(int[] data, int startInclude, int endExclude) {
        if (startInclude < endExclude && (endExclude - startInclude >= 2)) {
            int mid =((endExclude + startInclude) / 2);
            if (mid < endExclude) {
                sortPart(data, startInclude, mid);
                sortPart(data, mid, endExclude);
                mergeParts(data, startInclude, mid, endExclude);
            } else {
                sortPart(data, startInclude, mid);
            }
        }
    }

    public static void mergeParts(int[] data, int startInclude, int midIndex, int endExclude) {
        int firstStart = startInclude;
        int secondStart = midIndex;
        int firstCount = midIndex - startInclude;
        int secondCount = endExclude - midIndex;
        while (firstCount > 0 && secondCount > 0) {
            if (data[firstStart] <= data[secondStart]) {
                firstStart++;
                firstCount--;
            } else {
                int tempValue = data[secondStart];
                for (int i = secondStart; i > firstStart; i--) {
                    data[i] = data[i - 1];
                }
                data[firstStart] = tempValue;
                secondStart++;
                firstStart++;
                secondCount--;
            }
        }
    }
}
